class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0) {
          return true;
        }

        stack<char> stk;
        for (int i = 0; i < s.length(); ++i) {
          if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stk.push(s[i]);
          } else {
            if (stk.empty() ||
                 (s[i] == ')' && stk.top() != '(') ||
                 (s[i] == ']' && stk.top() != '[') ||
                 (s[i] == '}' && stk.top() != '{')) {
              return false;
            }
            stk.pop();
          }
        }
        return stk.empty();
    }
};
